<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns="http://www.w3.org/TR/REC-html40"><head>


<meta http-equiv="Content-Type" content="text/html; charset=windows-1252">
<meta name="ProgId" content="Word.Document">
<meta name="Generator" content="Microsoft Word 11">
<meta name="Originator" content="Microsoft Word 11">
<link rel="File-List" href="http://uva.onlinejudge.org/external/111/j_files/filelist.xml">
<link rel="Edit-Time-Data" href="http://uva.onlinejudge.org/external/111/j_files/editdata.mso">
<!--[if !mso]>
<style>
v\:* {behavior:url(#default#VML);}
o\:* {behavior:url(#default#VML);}
w\:* {behavior:url(#default#VML);}
.shape {behavior:url(#default#VML);}
</style>
<![endif]-->
<title>Problem J - Triple-Free Binary Strings</title>
<!--[if gte mso 9]><xml>
 <o:DocumentProperties>
  <o:Author>Shahriar Manzoor</o:Author>
  <o:LastAuthor>manzoor</o:LastAuthor>
  <o:Revision>101</o:Revision>
  <o:TotalTime>281</o:TotalTime>
  <o:Created>2004-05-14T06:35:00Z</o:Created>
  <o:LastSaved>2006-10-11T10:26:00Z</o:LastSaved>
  <o:Pages>1</o:Pages>
  <o:Words>152</o:Words>
  <o:Characters>869</o:Characters>
  <o:Company>ACM/ICPC</o:Company>
  <o:Lines>7</o:Lines>
  <o:Paragraphs>2</o:Paragraphs>
  <o:CharactersWithSpaces>1019</o:CharactersWithSpaces>
  <o:Version>11.5606</o:Version>
 </o:DocumentProperties>
</xml><![endif]--><!--[if gte mso 9]><xml>
 <w:WordDocument>
  <w:View>Print</w:View>
  <w:Zoom>120</w:Zoom>
  <w:SpellingState>Clean</w:SpellingState>
  <w:GrammarState>Clean</w:GrammarState>
  <w:ValidateAgainstSchemas/>
  <w:SaveIfXMLInvalid>false</w:SaveIfXMLInvalid>
  <w:IgnoreMixedContent>false</w:IgnoreMixedContent>
  <w:AlwaysShowPlaceholderText>false</w:AlwaysShowPlaceholderText>
  <w:BrowserLevel>MicrosoftInternetExplorer4</w:BrowserLevel>
 </w:WordDocument>
</xml><![endif]--><!--[if gte mso 9]><xml>
 <w:LatentStyles DefLockedState="false" LatentStyleCount="156">
 </w:LatentStyles>
</xml><![endif]-->
<style>
<!--
 /* Font Definitions */
 @font-face
	{font-family:"MS Mincho";
	panose-1:2 2 6 9 4 2 5 8 3 4;
	mso-font-alt:"\FF2D\FF33 \660E\671D";
	mso-font-charset:128;
	mso-generic-font-family:modern;
	mso-font-pitch:fixed;
	mso-font-signature:-1610612033 1757936891 16 0 131231 0;}
@font-face
	{font-family:"\@MS Mincho";
	panose-1:2 2 6 9 4 2 5 8 3 4;
	mso-font-charset:128;
	mso-generic-font-family:modern;
	mso-font-pitch:fixed;
	mso-font-signature:-1610612033 1757936891 16 0 131231 0;}
@font-face
	{font-family:Verdana;
	panose-1:2 11 6 4 3 5 4 4 2 4;
	mso-font-charset:0;
	mso-generic-font-family:swiss;
	mso-font-pitch:variable;
	mso-font-signature:536871559 0 0 0 415 0;}
 /* Style Definitions */
 p.MsoNormal, li.MsoNormal, div.MsoNormal
	{mso-style-parent:"";
	margin:0in;
	margin-bottom:.0001pt;
	mso-pagination:widow-orphan;
	font-size:12.0pt;
	mso-bidi-font-size:10.0pt;
	font-family:"Times New Roman";
	mso-fareast-font-family:"Times New Roman";
	color:black;}
h1
	{margin:0in;
	margin-bottom:.0001pt;
	mso-pagination:widow-orphan;
	mso-outline-level:1;
	font-size:12.0pt;
	font-family:"Times New Roman";
	color:black;
	font-weight:bold;}
h2
	{mso-style-next:Normal;
	margin:0in;
	margin-bottom:.0001pt;
	mso-pagination:widow-orphan;
	page-break-after:avoid;
	mso-outline-level:2;
	font-size:18.0pt;
	font-family:Arial;
	font-weight:bold;}
h3
	{mso-style-next:Normal;
	margin-top:12.0pt;
	margin-right:0in;
	margin-bottom:3.0pt;
	margin-left:0in;
	mso-pagination:widow-orphan;
	page-break-after:avoid;
	mso-outline-level:3;
	font-size:13.0pt;
	font-family:Arial;
	font-weight:bold;}
h4
	{mso-style-next:Normal;
	margin:0in;
	margin-bottom:.0001pt;
	mso-pagination:widow-orphan;
	page-break-after:avoid;
	mso-outline-level:4;
	font-size:12.0pt;
	mso-bidi-font-size:10.0pt;
	font-family:"Times New Roman";
	color:black;
	font-weight:normal;}
h5
	{mso-style-next:Normal;
	margin:0in;
	margin-bottom:.0001pt;
	mso-pagination:widow-orphan;
	mso-outline-level:5;
	font-size:12.0pt;
	mso-bidi-font-size:10.0pt;
	font-family:"Times New Roman";
	color:black;
	font-weight:normal;}
p.MsoHeader, li.MsoHeader, div.MsoHeader
	{margin:0in;
	margin-bottom:.0001pt;
	mso-pagination:widow-orphan;
	font-size:12.0pt;
	font-family:"Times New Roman";
	mso-fareast-font-family:"Times New Roman";}
p.MsoFooter, li.MsoFooter, div.MsoFooter
	{margin:0in;
	margin-bottom:.0001pt;
	mso-pagination:widow-orphan;
	font-size:12.0pt;
	font-family:"Times New Roman";
	mso-fareast-font-family:"Times New Roman";}
p.MsoCaption, li.MsoCaption, div.MsoCaption
	{mso-style-next:Normal;
	margin:0in;
	margin-bottom:.0001pt;
	mso-pagination:widow-orphan;
	font-size:18.0pt;
	font-family:Arial;
	mso-fareast-font-family:"Times New Roman";
	font-weight:bold;}
p.MsoBodyText, li.MsoBodyText, div.MsoBodyText
	{margin:0in;
	margin-bottom:.0001pt;
	text-align:justify;
	mso-pagination:widow-orphan;
	font-size:12.0pt;
	font-family:"Times New Roman";
	mso-fareast-font-family:"MS Mincho";
	mso-ansi-language:EN-GB;
	mso-fareast-language:SV;}
p.MsoBodyText2, li.MsoBodyText2, div.MsoBodyText2
	{margin:0in;
	margin-bottom:.0001pt;
	text-align:justify;
	mso-pagination:widow-orphan;
	font-size:12.0pt;
	mso-bidi-font-size:10.0pt;
	font-family:"Times New Roman";
	mso-fareast-font-family:"Times New Roman";
	color:black;
	mso-bidi-font-weight:bold;}
a:link, span.MsoHyperlink
	{color:#009999;
	mso-text-animation:none;
	text-decoration:none;
	text-underline:none;
	text-decoration:none;
	text-line-through:none;}
a:visited, span.MsoHyperlinkFollowed
	{color:purple;
	text-decoration:underline;
	text-underline:single;}
p
	{mso-margin-top-alt:auto;
	margin-right:0in;
	mso-margin-bottom-alt:auto;
	margin-left:0in;
	mso-pagination:widow-orphan;
	font-size:12.0pt;
	font-family:"Times New Roman";
	mso-fareast-font-family:"Times New Roman";}
pre
	{margin:0in;
	margin-bottom:.0001pt;
	mso-pagination:widow-orphan;
	tab-stops:45.8pt 91.6pt 137.4pt 183.2pt 229.0pt 274.8pt 320.6pt 366.4pt 412.2pt 458.0pt 503.8pt 549.6pt 595.4pt 641.2pt 687.0pt 732.8pt;
	font-size:10.0pt;
	font-family:"Courier New";
	mso-fareast-font-family:"Courier New";}
tt
	{font-family:"Courier New";
	mso-ascii-font-family:"Courier New";
	mso-fareast-font-family:"Courier New";
	mso-hansi-font-family:"Courier New";
	mso-bidi-font-family:"Courier New";}
p.preformatted, li.preformatted, div.preformatted
	{mso-style-name:preformatted;
	margin:0in;
	margin-bottom:.0001pt;
	mso-pagination:widow-orphan;
	layout-grid-mode:char;
	font-size:10.0pt;
	font-family:"Courier New";
	mso-fareast-font-family:"Times New Roman";}
p.paragraph, li.paragraph, div.paragraph
	{mso-style-name:paragraph;
	mso-margin-top-alt:auto;
	margin-right:0in;
	mso-margin-bottom-alt:auto;
	margin-left:0in;
	text-align:justify;
	mso-pagination:widow-orphan;
	font-size:12.0pt;
	font-family:"Times New Roman";
	mso-fareast-font-family:"Times New Roman";}
p.text, li.text, div.text
	{mso-style-name:text;
	mso-margin-top-alt:auto;
	margin-right:0in;
	mso-margin-bottom-alt:auto;
	margin-left:0in;
	mso-pagination:widow-orphan;
	font-size:8.0pt;
	font-family:Verdana;
	mso-fareast-font-family:"Times New Roman";
	mso-bidi-font-family:"Times New Roman";}
span.StyleArial16pt
	{mso-style-name:"Style Arial 16 pt";
	mso-ansi-font-size:16.0pt;
	font-family:Arial;
	mso-ascii-font-family:Arial;
	mso-hansi-font-family:Arial;
	mso-bidi-font-family:Arial;
	font-weight:bold;}
span.SpellE
	{mso-style-name:"";
	mso-spl-e:yes;}
span.GramE
	{mso-style-name:"";
	mso-gram-e:yes;}
@page Section1
	{size:595.45pt 841.7pt;
	margin:.8in .8in 67.7pt .8in;
	mso-header-margin:.5in;
	mso-footer-margin:.5in;
	mso-paper-source:0;}
div.Section1
	{page:Section1;}
-->
</style>
<!--[if gte mso 10]>
<style>
 /* Style Definitions */
 table.MsoNormalTable
	{mso-style-name:"Table Normal";
	mso-tstyle-rowband-size:0;
	mso-tstyle-colband-size:0;
	mso-style-noshow:yes;
	mso-style-parent:"";
	mso-padding-alt:0in 5.4pt 0in 5.4pt;
	mso-para-margin:0in;
	mso-para-margin-bottom:.0001pt;
	mso-pagination:widow-orphan;
	font-size:10.0pt;
	font-family:"Times New Roman";
	mso-ansi-language:#0400;
	mso-fareast-language:#0400;
	mso-bidi-language:#0400;}
</style>
<![endif]--><!--[if gte mso 9]><xml>
 <o:shapedefaults v:ext="edit" spidmax="9218"/>
</xml><![endif]--><!--[if gte mso 9]><xml>
 <o:shapelayout v:ext="edit">
  <o:idmap v:ext="edit" data="1"/>
 </o:shapelayout></xml><![endif]-->
</head><body style="" lang="EN-US" link="#009999" vlink="purple">

<div class="Section1">

<p class="MsoNormal" style="text-align: center;" align="center"><b style=""><span style="font-size: 28pt; font-family: Arial;">Problem J</span></b><span style="font-family: Arial;"><br>
</span><b style=""><span style="font-size: 20pt; font-family: Arial;">Triple-Free Binary Strings</span></b><b style=""><span style="font-size: 20pt; font-family: Arial;"> </span></b><span style="font-family: Arial;"><br>
<b style="">Input: </b>S<span style="">tandard Input<o:p></o:p></span></span></p>

<p class="MsoNormal" style="text-align: center;" align="center"><b style=""><span style="font-family: Arial;">Output: </span></b><span style="font-family: Arial;">Standard Output <o:p></o:p></span></p>

<p class="MsoNormal" style="text-align: center;" align="center"><span style="font-family: Arial;"><o:p>&nbsp;</o:p></span></p>

<pre style="text-align: justify; line-height: 14.4pt;"><span style="font-size: 12pt; font-family: &quot;Times New Roman&quot;; color: black;">A binary string consists of ones and zeros. Given a binary string T, <span class="GramE">if<span style="">&nbsp; </span>there</span> is no binary string S such that SSS (concatenate three copies of S together) is a substring of T, we say T is triple-free.<o:p></o:p></span></pre><pre style="text-align: justify; line-height: 14.4pt;"><span style="font-size: 12pt; font-family: &quot;Times New Roman&quot;; color: black;"><o:p>&nbsp;</o:p></span></pre><pre style="text-align: justify; line-height: 14.4pt;"><span style="font-size: 12pt; font-family: &quot;Times New Roman&quot;; color: black;">A pattern consists of ones, zeros and asterisks, where an <span class="GramE">asterisk(</span>*) can be replaced by either one or zero. For example, the pattern 0**1 contains strings 0001, 0011, 0101, 0111, but not 1001 or 0000.<o:p></o:p></span></pre><pre style="text-align: justify; line-height: 14.4pt;"><span style="font-size: 12pt; font-family: &quot;Times New Roman&quot;; color: black;"><o:p>&nbsp;</o:p></span></pre><pre style="text-align: justify; line-height: 14.4pt;"><span style="font-size: 12pt; font-family: &quot;Times New Roman&quot;; color: black;">Given a pattern P, how many triple-free binary strings does it contain?<o:p></o:p></span></pre><pre style=""><b><span style="font-size: 18pt; font-family: Arial;"><o:p>&nbsp;</o:p></span></b></pre><pre style="text-align: justify;"><b><span style="font-size: 18pt; font-family: Arial;">Input</span></b><span style="font-family: Arial;"><br>
</span><span style="font-size: 12pt; font-family: &quot;Times New Roman&quot;; color: black;">Each line of the input represents a test case, which contains the length of pattern, <span class="GramE">n(</span>0&lt;n&lt;31), and the pattern P. There can be maximum 35 test cases. <o:p></o:p></span></pre><pre style="text-align: justify; line-height: 14.4pt;"><span style="font-size: 12pt; font-family: &quot;Times New Roman&quot;; color: black;"><o:p>&nbsp;</o:p></span></pre><pre style="text-align: justify; line-height: 14.4pt;"><span style="font-size: 12pt; font-family: &quot;Times New Roman&quot;; color: black;">The input terminates when n=0.<o:p></o:p></span></pre><pre style=""><b><span style="font-size: 18pt; font-family: Arial;"><o:p>&nbsp;</o:p></span></b></pre><pre style="text-align: justify;"><b><span style="font-size: 18pt; font-family: Arial;">Output</span></b><span style="font-family: Arial;"><br>
</span><span style="font-size: 12pt; font-family: &quot;Times New Roman&quot;; color: black;">For each test case, print the case number and the answer, shown below. <o:p></o:p></span></pre>

<h1 style=""><span style="font-size: 18pt; font-family: Arial;"><o:p>&nbsp;</o:p></span></h1>

<h1 style=""><span style="font-size: 18pt; font-family: Arial;">Sample Input<span style="">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span><span style="">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</span>Output for Sample Input</span><span style="font-size: 18pt; font-family: Arial;"><o:p></o:p></span></h1>

<table class="MsoNormalTable" style="border: medium none ; background: rgb(204, 204, 204) none repeat scroll 0% 0%; -moz-background-clip: border; -moz-background-origin: padding; -moz-background-inline-policy: continuous; border-collapse: collapse;" border="1" cellpadding="0" cellspacing="0">
 <tbody><tr style="">
  <td style="border: 1pt solid windowtext; padding: 0in 5.4pt; width: 3.2in;" valign="top" width="307"><pre style="line-height: 14.4pt;"><span style="font-size: 11pt; color: black;">4 0**1<o:p></o:p></span></pre><pre style="line-height: 14.4pt;"><span style="font-size: 11pt; color: black;">5 *****<o:p></o:p></span></pre><pre style="line-height: 14.4pt;"><span style="font-size: 11pt; color: black;">10 **01**01**<o:p></o:p></span></pre><pre style="line-height: 14.4pt;"><span style="font-size: 11pt; color: black;">0<o:p></o:p></span></pre><pre><b><span style=""><o:p>&nbsp;</o:p></span></b></pre></td>
  <td style="border-style: solid solid solid none; border-color: windowtext windowtext windowtext -moz-use-text-color; border-width: 1pt 1pt 1pt medium; padding: 0in 5.4pt; width: 231.85pt;" valign="top" width="309"><pre><span style="font-size: 11pt;">Case 1: 2<o:p></o:p></span></pre><pre><span style="font-size: 11pt;">Case 2: 16<o:p></o:p></span></pre><pre><span style="font-size: 11pt;">Case 3: 9<o:p></o:p></span></pre><pre><span style="font-size: 11pt;"><o:p>&nbsp;</o:p></span></pre></td>
 </tr>
</tbody></table>

<div class="MsoNormal" style="text-align: center;" align="center"><span style="font-family: Arial; color: windowtext;">

<hr size="2" width="100%" align="center">

</span></div>

<p class="MsoNormal" style=""><span class="SpellE"><span style="font-family: Arial; color: windowtext;">Problemsetter</span></span><span style="font-family: Arial; color: windowtext;">: <span class="SpellE">Rujia</span> Liu</span><span style="font-family: Arial; color: windowtext;"><br>
Special Thanks: Shahriar Manzoor<span style=""><o:p></o:p></span></span></p>

<p class="MsoNormal" style="text-align: justify;"><o:p>&nbsp;</o:p></p>

</div>

</body></html>